// 一个机器人位于一个 m x n 网格的左上角。
// 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
// 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
// 网格中的障碍物和空位置分别用 1 和 0 来表示。
// 说明：m 和 n 的值均不超过 100。


function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const rows = obstacleGrid.length;// 读取行
  const cols = obstacleGrid[0].length;// 读取列
  // 边界位置：注意第一行第一列！
  obstacleGrid[0][0] = obstacleGrid[0][0] === 1 ? 0 : 1;
  // 第一行赋值为1,并对障碍物做赋0处理（注意计数器）
  for (let i = 1; i < cols; i++) {
    obstacleGrid[0][i] = obstacleGrid[0][i] === 1 ? 0 : obstacleGrid[0][i - 1];
  }
  // 第一列赋值为1,并对障碍物做赋0处理（注意计数器）
  for (let i = 1; i < rows; i++) {
    obstacleGrid[i][0] = obstacleGrid[i][0] === 1 ? 0 : obstacleGrid[i - 1][0];
  }
  // 根据条件转移方程开始计算路径总和
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      // 对障碍物做赋0处理
      if (obstacleGrid[i][j] === 1) {
        obstacleGrid[i][j] = 0;
        continue;
      }
      // 条件转移方程
      obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
    }
  }
  return obstacleGrid[rows - 1][cols - 1];
}

// 这道题目采用属于路径数量计算类型的问题，采用的是典型的动态规划算法求解
// 条件转移方程即当前网格的路径总和为上方网格的路径数量加上左方网格的路径数量
// 而动态规划的矩阵存储在这里我们可以直接使用原矩阵进行存储
// 具体操作上，首先需要注意第一行第一列这个位置。
// 因为它属于一个边界位置，可能会被赋值两遍，所以要拿出来特殊处理
// 然后我们之后需要做的主要是先为第一行和第一列分别做一个赋初值的处理（不然后续需要做一个边界的检测处理）
// 之后就是我们按照顺序依次得遍历整个矩阵，使用条件转移方程进行处理
// 在这里同样不要忘记在矩阵中是可能遇到障碍物的，要把障碍物赋值为0
// 遍历完整个矩阵后返回动态规划矩阵右下角的值即可。

